package i_Trie_;

import java.util.TreeMap;

/** @author 
 * 	public static void main(String[] args) {
		System.out.println(Character.forDigit(35, 36));
		System.out.println(Character.valueOf((char)97));
		
		char c = '9';
		int ic = 9;
		System.out.println(String.valueOf(ic).charAt(0));
		System.out.println(Character.forDigit(ic, 10));
		
		System.out.println(Character.MAX_RADIX);
		System.out.println(Character.MIN_RADIX);
	}
 *谈到char 容易混的几个地方
 *
 */
public class Trie {

    private class Node{

        public boolean isWord;
        public TreeMap<Character, Node> next;  //类似的结构使用HashMap会更快一些。如果规模较小直接使用数组是最快的，因为没有复杂操作；
/**
 * 我们在这一章的Trie中使用的TreeMap（红黑树）也是同理。红黑树中由于有复杂的旋转操作（在这个课程的第十三章会介绍），
 * 虽然整体平均复杂度更低，但是对于小样本数据，是没有太大的性能优势的。所以，在这里，其实使用HashMap代替更好。
 * 如果你能保证你存储的单词只包含小写字母，直接使用数组将是更快的：）
 * 
 */
        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
        root = new Node();
        size = 0;
    }

    // 获得Trie中存储的单词数量
    public int getSize(){
        return size;
    }

    // 向Trie中添加一个新的单词word
    public void add(String word){

        Node cur = root;
        for(int i = 0 ; i < word.length() ; i ++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }

        if(!cur.isWord){
            cur.isWord = true;
            size ++;
        }
    }

    // 查询单词word是否在Trie中
    public boolean contains(String word){

        Node cur = root;
        for(int i = 0 ; i < word.length() ; i ++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }

    // 查询是否在Trie中有单词以prefix为前缀
    public boolean isPrefix(String prefix){

        Node cur = root;
        for(int i = 0 ; i < prefix.length() ; i ++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null)
                return false;
            cur = cur.next.get(c);
        }

        return true;
    }
}
